{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Knight Dialer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: knightDialer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #骑士拨号器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>象棋骑士有一个<strong>独特的移动方式</strong>，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个&nbsp;<strong>L&nbsp;</strong>的形状)。</p>\n",
    "\n",
    "<p>象棋骑士可能的移动方式如下图所示:</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/18/chess.jpg\" style=\"height: 200px; width: 200px;\" /></p>\n",
    "\n",
    "<p>我们有一个象棋骑士和一个电话垫，如下所示，骑士<strong>只能站在一个数字单元格上</strong>(即蓝色单元格)。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/18/phone.jpg\" style=\"height: 200px; width: 150px;\" /></p>\n",
    "\n",
    "<p>给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。</p>\n",
    "\n",
    "<p>你可以将骑士放置在<strong>任何数字单元格</strong>上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是<strong>有效</strong>的骑士跳跃。</p>\n",
    "\n",
    "<p>因为答案可能很大，<strong>所以输出答案模&nbsp;</strong><code>10<sup>9</sup>&nbsp;+ 7</code>.</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3131\n",
    "<strong>输出：</strong>136006598\n",
    "<strong>解释：</strong>注意取模\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [knight-dialer](https://leetcode.cn/problems/knight-dialer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [knight-dialer](https://leetcode.cn/problems/knight-dialer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '3131']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        dp = [1]*10\n",
    "        moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],\n",
    "                     [1,7,0],[2,6],[1,3],[2,4]]\n",
    "\n",
    "        for i in range(n-1):\n",
    "            dp2 = [0]*10\n",
    "            for st, cnt in enumerate(moves):\n",
    "                for k in cnt:\n",
    "                    dp2[k] += dp[st]\n",
    "                    dp2[k] %= MOD\n",
    "            \n",
    "            dp = dp2\n",
    "\n",
    "        return sum(dp)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        a, b, c, d, e, f, h, i, j, k = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\n",
    "        for _ in range(n - 1):\n",
    "            a, b, c, d, e, f, h, i, j, k = f + i, h + j, d + i, c + j + k, 0, a + h + k, b + f, a + c, b + d, d + f\n",
    "        return (a + b + c + d + e + f + h + i + j + k) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp=[[0,0,0,0] for i in range(n)]\n",
    "        dp[0]=[2,4,1,2]\n",
    "        if n==1:\n",
    "            return 10\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]\n",
    "            dp[i][1]=((dp[i-1][0]+dp[i-1][3])*2)%1000000007\n",
    "            dp[i][2]=dp[i-1][3]\n",
    "            dp[i][3]=(dp[i-1][1]+dp[i-1][2]*2)%1000000007\n",
    "        return sum(dp[-1])%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp = []\n",
    "        for i in range(10):\n",
    "            dp.append([0, 1])\n",
    "\n",
    "        mod = 1000000007\n",
    "\n",
    "        # 进行动态规划，自底向上\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            dp[0].append(((dp[4][i - 1] + dp[6][i - 1]) % mod))\n",
    "            dp[1].append(((dp[6][i - 1] + dp[8][i - 1]) % mod))\n",
    "            dp[2].append(((dp[7][i - 1] + dp[9][i - 1]) % mod))\n",
    "            dp[3].append(dp[1][i])\n",
    "            dp[4].append((dp[0][i - 1] + dp[3][i - 1] + dp[9][i - 1]) % mod)\n",
    "            dp[5].append(0)\n",
    "            dp[6].append(dp[4][i])\n",
    "            dp[7].append(((dp[2][i - 1] + dp[6][i - 1]) % mod))\n",
    "            dp[8].append(((dp[1][i - 1] + dp[3][i - 1]) % mod))\n",
    "            dp[9].append(dp[7][i])\n",
    "\n",
    "        # 進行相加\n",
    "        result = 0\n",
    "        for i in range(10):\n",
    "            result = (result + dp[i][n]) % mod\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        dp = [4, 9, 20, 46] + [0]*(n-3)\n",
    "        for i in range(4, n+1):\n",
    "            dp[i] = 6 * dp[i-2] - 4 * dp[i-4]\n",
    "\n",
    "        return dp[n] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1: return 10\n",
    "        mod = 10**9 + 7\n",
    "        dest = [[4, 6],\n",
    "                [6, 8],\n",
    "                [7, 9],\n",
    "                [4, 8],\n",
    "                [0, 3, 9],\n",
    "                [],\n",
    "                [0, 1, 7],\n",
    "                [2, 6],\n",
    "                [1, 3],\n",
    "                [2, 4]]\n",
    "        dp = [[0]*10 for i in range(n+1)]\n",
    "        dp[1] = [1] * 10\n",
    "        for i in range(2, n+1):\n",
    "            for digit in range(10):\n",
    "                for next_digit in dest[digit]:\n",
    "                    dp[i][digit] = (dp[i][digit] + dp[i-1][next_digit]) % mod\n",
    "        return sum(dp[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp = [[[0 for _ in range(3)] for _ in range(4)] for _ in range(n)]\n",
    "        for i in range(4):\n",
    "            for j in range(3):\n",
    "                dp[0][i][j] = 1\n",
    "        dp[0][3][0] = 0\n",
    "        dp[0][3][2] = 0\n",
    "\n",
    "        dirs = [(1, 2), (-1, -2), (-1, 2), (1, -2),\n",
    "                (2, 1), (-2, -1), (-2, 1), (2, - 1)]\n",
    "        mod = 1e9 + 7\n",
    "        for k in range(1, n):\n",
    "            for i in range(4):\n",
    "                for j in range(3):\n",
    "                    if i == 3 and j != 1:\n",
    "                        continue\n",
    "                    for d in dirs:\n",
    "                        x, y = i + d[0], j + d[1]\n",
    "                        if 0 <= x < 4 and 0 <= y < 3:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][x][y]) % mod\n",
    "        res = sum(dp[n - 1][i][j] for i in range(4) for j in range(3))\n",
    "        return int(res % mod)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        a = [0]*(n+1) #在0截止\n",
    "        a[1] = 1\n",
    "        b = [0]*(n+1) #在46截止\n",
    "        b[1] = 2\n",
    "        c = [0]*(n+1) #在1379截止\n",
    "        c[1] = 4\n",
    "        d = [0]*(n+1) #在28截止\n",
    "        d[1] = 2\n",
    "        for i in range(1,n):\n",
    "            a[i+1] = b[i]\n",
    "            b[i+1] = a[i]*2 + c[i]\n",
    "            c[i+1] = b[i]*2 + d[i]*2\n",
    "            d[i+1] = c[i]\n",
    "        return (a[n] + b[n] + c[n] + d[n]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        route = {\n",
    "            1:[6,8],\n",
    "            2:[7,9],\n",
    "            3:[8,4],\n",
    "            4:[3,9,0],\n",
    "            5:[],\n",
    "            6:[1,7,0],\n",
    "            7:[6,2],\n",
    "            8:[1,3],\n",
    "            9:[4,2],\n",
    "            0:[4,6]\n",
    "\n",
    "        }\n",
    "        def move(a):\n",
    "            return route[a]\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def get_res(n):\n",
    "            if n==1:\n",
    "                res = {x:1 for x in range(10)}\n",
    "            else:\n",
    "                end = get_res(n-1)\n",
    "                res = defaultdict(int)\n",
    "                for x in end:\n",
    "                    repeat = end[x]\n",
    "                    for y in route[x]:\n",
    "                        res[y] += repeat\n",
    "            return res\n",
    "        res = get_res(n)\n",
    "        res = sum(list(res.values()))\n",
    "        # print(res)\n",
    "        return res%(10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        # if n == 1:\n",
    "        #     return 10\n",
    "        self.next = {}\n",
    "        self.next[0] = [4, 6]\n",
    "        self.next[1] = [6, 8]\n",
    "        self.next[2] = [7, 9]\n",
    "        self.next[3] = [4, 8]\n",
    "        self.next[4] = [0, 3, 9]\n",
    "        self.next[6] = [0, 1, 7]\n",
    "        self.next[7] = [2, 6]\n",
    "        self.next[8] = [1, 3]\n",
    "        self.next[9] = [2, 4]\n",
    "\n",
    "        dialer = self.findDialer(n)\n",
    "        # print (dialer)\n",
    "        ans = 0\n",
    "        for k in dialer.keys():\n",
    "            ans += dialer[k]\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n",
    "        \n",
    "    def findDialer(self, n):\n",
    "        if n == 1:\n",
    "            ans = {}\n",
    "            for i in range(10):\n",
    "                ans[i] = 1\n",
    "            return ans\n",
    "        \n",
    "        dialer = self.findDialer(n - 1)\n",
    "        ans = {}\n",
    "        for i in range(10):\n",
    "            ans[i] = 0\n",
    "        for k in dialer.keys():\n",
    "            if k in self.next:\n",
    "                for nk in self.next[k]:\n",
    "                    ans[nk] += dialer[k]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp = [[[0 for _ in range(7)] for _ in range(8)] for _ in range(n)]\n",
    "        for i in range(2,5):\n",
    "            for j in range(2,5):\n",
    "                dp[0][i][j] = 1\n",
    "        dp[0][5][3] = 1\n",
    "\n",
    "        for k in range(1,n):\n",
    "            for i in range(2,5):\n",
    "                for j in range(2,5):\n",
    "                    dp[k][i][j] = (dp[k-1][i-2][j-1] + dp[k-1][i-2][j+1]+dp[k-1][i-1][j-2] + dp[k-1][i-1][j+2]+dp[k-1][i+2][j-1] + dp[k-1][i+2][j+1]+dp[k-1][i+1][j-2] + dp[k-1][i+1][j+2])%(10**9+7)\n",
    "                    \n",
    "            dp[k][5][3] = (dp[k-1][4][1]+dp[k-1][4][5]+dp[k-1][3][2]+dp[k-1][3][4]+dp[k-1][6][1]+dp[k-1][6][5]+dp[k-1][7][2]+dp[k-1][7][4])%(10**9+7)\n",
    "        #print(dp)\n",
    "        res = (dp[n-1][2][2]+ dp[n-1][2][3]+dp[n-1][2][4]+dp[n-1][3][2]+ dp[n-1][3][3]+ dp[n-1][3][4]+dp[n-1][4][2]+ dp[n-1][4][3]+ dp[n-1][4][4]+dp[n-1][5][3])%(10**9+7)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        neighbors = defaultdict(list)\n",
    "        neighbors[0] = [4,6]\n",
    "        neighbors[1] = [6,8]\n",
    "        neighbors[2] = [7,9]\n",
    "        neighbors[3] = [4,8]\n",
    "        neighbors[4] = [0,3,9]\n",
    "        neighbors[5] = []\n",
    "        neighbors[6] = [0,1,7]\n",
    "        neighbors[7] = [2,6]\n",
    "        neighbors[8] = [1,3]\n",
    "        neighbors[9] = [2,4]\n",
    "\n",
    "        equal = [0,1,2,1,4,5,4,1,2,1]\n",
    "        refresh = [0,1,2,4]\n",
    "        # ans = [[1] * 6 for i in range(2)]\n",
    "        # for i in range(1,n):\n",
    "        #     ans[i%2] = [0] * 6\n",
    "        #     for num in refresh:\n",
    "        #         for j in neighbors[num]:\n",
    "        #             ans[i%2][num] += ans[(i-1)%2][equal[j]]\n",
    "        #     # print(ans)\n",
    "        #     for num in refresh:\n",
    "        #         ans[i%2][num] %= 10**9+7\n",
    "        # return sum([ans[(n-1)%2][equal[num]] for num in range(10)])%(10**9+7)\n",
    "        ans = 0\n",
    "        @lru_cache\n",
    "        def validNum(num, n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            count = 0\n",
    "            for i in neighbors[num]:\n",
    "                count += validNum(equal[i], n-1)\n",
    "            if count >= 10**9+7:\n",
    "                count %= 10**9+7\n",
    "            return count\n",
    "        for i in range(10):\n",
    "            ans += validNum(i, n)\n",
    "        return ans%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dial_dict = {\n",
    "            0: [4, 6],\n",
    "            1: [6, 8],\n",
    "            2: [7, 9],\n",
    "            3: [4, 8],\n",
    "            4: [3, 9, 0],\n",
    "            5: [],\n",
    "            6: [1, 7, 0],\n",
    "            7: [2, 6],\n",
    "            8: [1, 3],\n",
    "            9: [2, 4]\n",
    "        }\n",
    "        \n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(cur_number, cnt):\n",
    "            nonlocal ans\n",
    "            if cnt == n:\n",
    "                return 1\n",
    "            cur_ans = 0\n",
    "            for no in dial_dict[cur_number]:\n",
    "                cur_ans += dfs(no, cnt + 1) % mod\n",
    "            return cur_ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(0, 10):\n",
    "            ans += dfs(i, 1) % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        mod = (10**9 + 7)\n",
    "        move_tble = {1:[6,8],2:[7,9],3:[4,8],4:[0,3,9],5:[],6:[0,1,7],7:[2,6],8:[1,3],9:[2,4],0:[4,6]}\n",
    "        @lru_cache\n",
    "        def f(num, steps):\n",
    "            nonlocal mod\n",
    "            if steps == 1: return 1\n",
    "            else: \n",
    "                res = 0\n",
    "                for i in move_tble[num]:\n",
    "                    res += (f(i, steps-1) % mod)\n",
    "                return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in [1,4,7]:\n",
    "            ans += (2 * f(i, n) % mod)\n",
    "        for i in [2,5,8,0]:\n",
    "            ans += (f(i,n) % mod)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N: int) -> int:\n",
    "        pic = {1: [6, 8], 2: [7, 9], 3:[4, 8], 4:[0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6], 8: [1, 3], 9: [2, 4], 0: [4, 6]}\n",
    "        hashmap = {}; res = 0\n",
    "        for i in range(10):\n",
    "            res += self.helper(N - 1, i, pic, hashmap)\n",
    "        return res % 1000000007\n",
    "    def helper(self, n, num, pic, hashmap):\n",
    "        if (num, n) in hashmap:\n",
    "            return hashmap[(num, n)]\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        count = 0\n",
    "        for x in pic[num]:\n",
    "            count += self.helper(n - 1, x, pic, hashmap) % 1000000007\n",
    "        hashmap[(num, n)] = count % 1000000007\n",
    "        return count % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N: int) -> int:\n",
    "        pic = {1: [6, 8], 2: [7, 9], 3:[4, 8], 4:[0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6], 8: [1, 3], 9: [2, 4], 0: [4, 6]}\n",
    "        hashmap = {}; res = 0\n",
    "        for i in range(10):\n",
    "            res += self.helper(N - 1, i, pic, hashmap)\n",
    "        return res % 1000000007\n",
    "    def helper(self, n, num, pic, hashmap):\n",
    "        if (num, n) in hashmap:\n",
    "            return hashmap[(num, n)]\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        count = 0\n",
    "        for x in pic[num]:\n",
    "            count += self.helper(n - 1, x, pic, hashmap) % 1000000007\n",
    "        hashmap[(num, n)] = count % 1000000007\n",
    "        return count % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "dct = dict()\n",
    "dct[0] = [4, 6]\n",
    "dct[1] = [6, 8]\n",
    "dct[2] = [7, 9]\n",
    "dct[3] = [4, 8]\n",
    "dct[4] = [3, 9, 0]\n",
    "dct[5] = []\n",
    "dct[6] = [1, 7, 0]\n",
    "dct[7] = [2, 6]\n",
    "dct[8] = [1, 3]\n",
    "dct[9] = [2, 4]\n",
    "\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(n, d):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    res = 0\n",
    "    for y in dct[d]:\n",
    "        res += dfs(n - 1, y)\n",
    "    return res % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        return sum(dfs(n, d) for d in range(10)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict, List, Tuple\n",
    "\n",
    "M = 4\n",
    "N = 3\n",
    "BADS = { 30, 32 }\n",
    "MOD = 10 ** 9 + 7\n",
    "dirs:List[Tuple[int, int]] = [(2, 1), (1, 2), (-2, -1), (-1, -2), (1, -2), (2, -1), (-1, 2), (-2, 1)]\n",
    "\n",
    "class Solution:\n",
    "    cache:Dict[int, int]\n",
    "\n",
    "    def dfs(self, pos:Tuple[int, int], n:int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        k = (pos[0] * 10 + pos[1]) * 5005 + n\n",
    "        if k in self.cache:\n",
    "            return self.cache[k]\n",
    "        res = 0\n",
    "        for dx, dy in dirs:\n",
    "            x, y = pos[0] + dx, pos[1] + dy\n",
    "            if x * 10 + y in BADS or not (0 <= x < M and 0 <= y < N):\n",
    "                continue\n",
    "            res = (res + self.dfs((x, y), n - 1)) % MOD\n",
    "        self.cache[k] = res\n",
    "        return res\n",
    "\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        self.cache = {}\n",
    "        res = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if i * 10 + j in BADS:\n",
    "                    continue\n",
    "                res = (res + self.dfs((i, j), n)) % MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.transfer_matr = np.array([\n",
    "            [0,0,0,0,1,0,1,0,0,0],\n",
    "            [0,0,0,0,0,0,1,0,1,0],\n",
    "            [0,0,0,0,0,0,0,1,0,1],\n",
    "            [0,0,0,0,1,0,0,0,1,0],\n",
    "            [1,0,0,1,0,0,0,0,0,1],\n",
    "            [0,0,0,0,0,0,0,0,0,0],\n",
    "            [1,1,0,0,0,0,0,1,0,0],\n",
    "            [0,0,1,0,0,0,1,0,0,0],\n",
    "            [0,1,0,1,0,0,0,0,0,0],\n",
    "            [0,0,1,0,1,0,0,0,0,0],\n",
    "            ], dtype=np.int64)\n",
    "        self.states = np.array([1,]*10, dtype=np.int64)\n",
    "    def knightDialer(self, N: int) -> int:\n",
    "        for _ in range(N-1):\n",
    "            self.states = np.matmul(self.transfer_matr, self.states)\n",
    "            self.states = np.mod(self.states, (10**9+7))\n",
    "        return sum(self.states) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(remain, k, mapping, dp):\n",
    "    if remain == 1:\n",
    "        return 1\n",
    "    if (remain, k) in dp:\n",
    "        return dp[(remain, k)]\n",
    "    res = 0\n",
    "    for item in mapping[k]:\n",
    "        res += dfs(remain-1, item, mapping, dp)\n",
    "        res %= ((10 ** 9)+7)\n",
    "    dp[(remain, k)] = res\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        mapping = {\n",
    "            0: (4, 6),\n",
    "            1: (6, 8),\n",
    "            2: (7, 9),\n",
    "            3: (4, 8),\n",
    "            4: (3, 9, 0),\n",
    "            5: (),\n",
    "            6: (1, 7, 0),\n",
    "            7: (2, 6),\n",
    "            8: (1, 3),\n",
    "            9: (2, 4)\n",
    "        }\n",
    "        dp = {}\n",
    "        res = 0\n",
    "        for i in range(10):\n",
    "            res += dfs(n, i, mapping, dp)\n",
    "            res %= (1e9 + 7)\n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        \n",
    "        # step_map = {1 : (6, 8), 2 : (7, 9), 3: (4, 8), 4 : (3, 9), 5 : (), 6 : (1, 7), 7 : (2, 6), 8 : (1, 3), 9 : (2, 4), 0 : (4, 6)}\n",
    "        step_map = {1 : (6, 8), 2 : (7, 9), 3: (4, 8), 4 : (0, 3, 9), 6 : (0, 1, 7), 7 : (2, 6), 8 : (1, 3), 9 : (2, 4), 0 : (4, 6)}\n",
    "        info = {}\n",
    "        res = 0\n",
    "        tmp = None\n",
    "\n",
    "        for k in (1, 4, 7):\n",
    "            tmp = self.recurse(k, step_map, n, info)\n",
    "            res += (tmp << 1)\n",
    "            if res >= 1000000007:\n",
    "                res %= 1000000007\n",
    "        \n",
    "        for k in (2, 8, 0):\n",
    "            tmp = self.recurse(k, step_map, n, info)\n",
    "            res += tmp\n",
    "            if res >= 1000000007:\n",
    "                res %= 1000000007\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def recurse(self, k, step_map, n, info):\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        if info.get((k, n), None) is not None:\n",
    "            return info[(k, n)]\n",
    "        \n",
    "        res = 0\n",
    "        # print(step_map, k)\n",
    "        for next_k in step_map[k]:\n",
    "            res += self.recurse(next_k, step_map, n - 1, info)\n",
    "        \n",
    "        if res >= 1000000007:\n",
    "            res %= 1000000007\n",
    "        \n",
    "        info[(k, n)] = res\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        mp = {}\n",
    "        mp[0] = [4,6]\n",
    "        mp[1] = [6, 8]\n",
    "        mp[2] = [7, 9]\n",
    "        mp[3] = [4, 8]\n",
    "        mp[4] = [3, 9, 0]\n",
    "        mp[5] = []\n",
    "        mp[6] = [1, 7, 0]\n",
    "        mp[7] = [2, 6]\n",
    "        mp[8] = [1, 3]\n",
    "        mp[9] = [2, 4]\n",
    "        @cache\n",
    "        def dfs(d,n):\n",
    "            if n==1:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nxt in mp[d]:\n",
    "                cnt += dfs(nxt,n-1)\n",
    "            return cnt%MOD\n",
    "        ans = 0\n",
    "        for d in range(10):\n",
    "            ans += dfs(d,n)\n",
    "        dfs.cache_clear()\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "\n",
    "        jump_dict = {\n",
    "            1: [6, 8],\n",
    "            2: [7, 9],\n",
    "            3: [4, 8],\n",
    "            4: [3, 9, 0],\n",
    "            5: [],\n",
    "            6: [1, 7, 0],\n",
    "            7: [2, 6],\n",
    "            8: [1, 3],\n",
    "            9: [2, 4],\n",
    "            0: [4, 6]\n",
    "        }\n",
    "\n",
    "        MOD = 1e9 + 7\n",
    "\n",
    "        def dfs(x, step_left, cache):\n",
    "            if (x, step_left) in cache:\n",
    "                return cache[(x, step_left)]\n",
    "            if step_left == 0:\n",
    "                cache[(x, step_left)] = 1\n",
    "                return 1\n",
    "            if step_left == 1:\n",
    "                cache[(x, step_left)] = len(jump_dict[x])\n",
    "                return cache[(x, step_left)]\n",
    "            \n",
    "            res = 0\n",
    "            next_x_list = jump_dict[x]\n",
    "            for next_x in next_x_list:\n",
    "                sub_res = dfs(next_x, step_left-1, cache)\n",
    "                sub_res = int(sub_res % MOD)\n",
    "                res += sub_res\n",
    "                res = int(res % MOD)\n",
    "            \n",
    "            cache[(x, step_left)] = res\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        cache = {}\n",
    "        for x in jump_dict.keys():\n",
    "            ans += dfs(x, n-1, cache)\n",
    "            ans = int(ans % MOD)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        direct = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]\n",
    "        is_vaild = set()\n",
    "        for i in range(4):\n",
    "            for j in range(3):\n",
    "                if i==3 and (j == 0 or j==2):\n",
    "                    continue\n",
    "                is_vaild.add((i,j))\n",
    "        @cache\n",
    "        def dfs(x,y,n):\n",
    "            if n==1:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nx,ny in direct:\n",
    "                dx,dy = x+nx,y+ny\n",
    "                if (dx,dy) in is_vaild:\n",
    "                    cnt += dfs(dx,dy,n-1)\n",
    "            return cnt%MOD\n",
    "        ans = 0\n",
    "        for x,y in is_vaild:\n",
    "            ans += dfs(x,y,n)\n",
    "        dfs.cache_clear()\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dic = {\n",
    "            0: [4, 6],\n",
    "            1: [6, 8],\n",
    "            2: [7, 9],\n",
    "            3: [4, 8],\n",
    "            4: [0, 3, 9],\n",
    "            5: [],\n",
    "            6: [0, 1, 7],\n",
    "            7: [2, 6],\n",
    "            8: [1, 3],\n",
    "            9: [2, 4],\n",
    "        }\n",
    "\n",
    "        dp = [[0 for _ in range(10)] for _ in range(5000)]\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        def dfs(n, cur_num):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            \n",
    "            # already in memo, return all combinations\n",
    "            if dp[n][cur_num] != 0:\n",
    "                return dp[n][cur_num]\n",
    "            \n",
    "\n",
    "            res = 0\n",
    "            for num in dic[cur_num]:\n",
    "                res += dfs(n - 1, num)\n",
    "            \n",
    "            res = res % mod\n",
    "            dp[n][cur_num] = res\n",
    "            return res\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(10):\n",
    "            res += dfs(n - 1, i)\n",
    "        return res % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "\n",
    "    def knightDialer(self, N):\n",
    "        if N == 1:\n",
    "            return 10\n",
    "        m = numpy.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],\n",
    "                          [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],\n",
    "                          [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],\n",
    "                          [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],\n",
    "                          [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],\n",
    "                          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "                          [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],\n",
    "                          [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],\n",
    "                          [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],\n",
    "                          [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])\n",
    "        res = 1\n",
    "        N -= 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        while N:\n",
    "            if N % 2:\n",
    "                res = res * m % mod\n",
    "                N -= 1\n",
    "            m = m * m % mod\n",
    "            N /= 2\n",
    "        return int(numpy.sum(res)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        # reach = ((4, 6), (6, 8), (7, 9), (4, 8), (3, 9, 0), (), (1, 7, 0), (2, 6), (1, 3), (2, 4))\n",
    "        # M = [[0] * 10 for _ in range(n)]\n",
    "        # M[0] = [1]*10\n",
    "        # for step in range(1, n):\n",
    "        #     for tile in range(10):\n",
    "        #         for nxt in reach[tile]:\n",
    "        #             M[step][nxt] += M[step-1][tile]\n",
    "        # return sum(M[-1]) % (10** 9 + 7)\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return 10\n",
    "        # nums = [1, 1, 1, 1]\n",
    "        # for i in range(n - 1):\n",
    "        #     nums = [nums[1] + nums[2], 2 * nums[0], 2 * nums[0] + nums[3], 2 * nums[2]]\n",
    "        # return (4 * nums[0] + 2 * nums[1] + 2 * nums[2] + nums[3]) % 1000000007\n",
    "\n",
    "        import numpy as np\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        mat =np.array([[0,1,1,0],[2,0,0,0],[2,0,0,1],[0,0,2,0]],dtype= object)\n",
    "        res = np.linalg.matrix_power(mat,n-1)\n",
    "        res = res @ [1,1,1,1]\n",
    "        return int(res[0] *4 + res[1] * 2 + res[2] * 2 + res[3]) % (10** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        # memo = ((4, 6), (6, 8), (7, 9), (4, 8), (3, 9, 0), (), (1, 7, 0), (2, 6), (1, 3), (2, 4))\n",
    "        # ans = [[0] * 10 for _ in range(n)]\n",
    "        # ans[0] = [1]*10\n",
    "        # for x in range(1, n):\n",
    "        #     for y in range(10):\n",
    "        #         for z in reach[y]:\n",
    "        #             M[x][z] += M[x-1][y]\n",
    "        # return sum(ans[-1]) % (10** 9 + 7)\n",
    "\n",
    "        # if n == 1:\n",
    "        #     return 10\n",
    "        # nums = [1, 1, 1, 1]\n",
    "        # for i in range(n - 1):\n",
    "        #     nums = [nums[1] + nums[2], 2 * nums[0], 2 * nums[0] + nums[3], 2 * nums[2]]\n",
    "        # return (4 * nums[0] + 2 * nums[1] + 2 * nums[2] + nums[3]) % 1000000007\n",
    "\n",
    "        import numpy as np\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        mat =np.array([[0,1,1,0],[2,0,0,0],[2,0,0,1],[0,0,2,0]],dtype= object)\n",
    "        res = np.linalg.matrix_power(mat,n-1)\n",
    "        res = res @ [1,1,1,1]\n",
    "        return int(res[0] *4 + res[1] * 2 + res[2] * 2 + res[3]) % (10** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp = [[1 for j in range(10)] for i in range(n)]\n",
    "        for i in range(n-1):\n",
    "            dp[i+1][1] = dp[i][8]+dp[i][6]\n",
    "            dp[i+1][2] = dp[i][7]+dp[i][9]\n",
    "            dp[i+1][3] = dp[i][4]+dp[i][8]\n",
    "            dp[i+1][4] = dp[i][3]+dp[i][9]+dp[i][0]\n",
    "            dp[i+1][5] = 0\n",
    "            dp[i+1][6] = dp[i][1]+dp[i][7]+dp[i][0]\n",
    "            dp[i+1][7] = dp[i][2]+dp[i][6]\n",
    "            dp[i+1][8] = dp[i][1]+dp[i][3]\n",
    "            dp[i+1][9] = dp[i][2]+dp[i][4]\n",
    "            dp[i+1][0] = dp[i][4]+dp[i][6]\n",
    "        return sum(dp[-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        hash_ = {1:[6, 8], 2:[7, 9], 3:[4, 8], 4:[0, 3, 9], 5:[], 6:[0, 1, 7], 7:[2, 6], 8:[1, 3], 9:[2, 4], 0:[4, 6]}\n",
    "        dp = [[0]*10 for _ in range(n)]\n",
    "        for i in range(10):\n",
    "            dp[0][i] = 1 \n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(10):\n",
    "                for item in hash_[j]:\n",
    "                    dp[i][j] += dp[i-1][item]\n",
    "\n",
    "        return sum(dp[-1]) % (10**9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def knightDialer(self, n: int) -> int:\r\n",
    "        dp = [[0] * 10 for _ in range(n)] # dp[i][j] i jumps stops at j\r\n",
    "\r\n",
    "        for j in range(10):\r\n",
    "            dp[0][j] = 1\r\n",
    "\r\n",
    "        for i in range(1, n):\r\n",
    "            dp[i][0] = dp[i-1][4] + dp[i-1][6]\r\n",
    "            dp[i][1] = dp[i-1][6] + dp[i-1][8]\r\n",
    "            dp[i][2] = dp[i-1][7] + dp[i-1][9]\r\n",
    "            dp[i][3] = dp[i-1][4] + dp[i-1][8]\r\n",
    "            dp[i][4] = dp[i-1][3] + dp[i-1][9] + dp[i-1][0]\r\n",
    "            dp[i][6] = dp[i-1][1] + dp[i-1][7] + dp[i-1][0]\r\n",
    "            dp[i][7] = dp[i-1][2] + dp[i-1][6]\r\n",
    "            dp[i][8] = dp[i-1][1] + dp[i-1][3]\r\n",
    "            dp[i][9] = dp[i-1][2] + dp[i-1][4]\r\n",
    "        return sum(dp[-1][j] for j in range(10)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[1] * 10 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i][1] = dp[i - 1][6] + dp[i - 1][8]\n",
    "            dp[i][2] = dp[i - 1][7] + dp[i - 1][9]\n",
    "            dp[i][3] = dp[i - 1][4] + dp[i - 1][8]\n",
    "            dp[i][4] = dp[i - 1][3] + dp[i - 1][9] + dp[i - 1][0]\n",
    "            dp[i][5] = 0\n",
    "            dp[i][6] = dp[i - 1][1] + dp[i - 1][7] + dp[i - 1][0]\n",
    "            dp[i][7] = dp[i - 1][2] + dp[i - 1][6]\n",
    "            dp[i][8] = dp[i - 1][1] + dp[i - 1][3]\n",
    "            dp[i][9] = dp[i - 1][2] + dp[i - 1][4]\n",
    "            dp[i][0] = dp[i - 1][4] + dp[i - 1][6]\n",
    "        return sum(dp[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dp=[[0 for _ in range(10)] for _ in range(n)]\n",
    "        for i in range(10):\n",
    "            dp[0][i]=1\n",
    "            \n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][4]+dp[i-1][6]\n",
    "            dp[i][1]=dp[i-1][6]+dp[i-1][8]\n",
    "            dp[i][2]=dp[i-1][7]+dp[i-1][9]\n",
    "            dp[i][3]=dp[i-1][4]+dp[i-1][8]\n",
    "            dp[i][4]=dp[i-1][0]+dp[i-1][3]+dp[i-1][9]\n",
    "            dp[i][6]=dp[i-1][0]+dp[i-1][1]+dp[i-1][7]\n",
    "            dp[i][7]=dp[i-1][2]+dp[i-1][6]\n",
    "            dp[i][8]=dp[i-1][1]+dp[i-1][3]\n",
    "            dp[i][9]=dp[i-1][2]+dp[i-1][4]\n",
    "        return sum(dp[n-1])%(7+10**9)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        number = [[1,2,3],[4,5,6],[7,8,9],[-1,0,-1]]\n",
    "        row, col = len(number), len(number[0])\n",
    "        \n",
    "        dp = [[[0]*col for _ in range(row)] for _ in range(n+1)]\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if (i==3 and j==0) or (i==3 and j==2):\n",
    "                    continue\n",
    "                dp[0][i][j] = 1\n",
    "\n",
    "        print(dp)\n",
    "        for time in range(1,n+1):\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    for newi, newj in[(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1)]:\n",
    "                        if newi<0 or newi>=4 or newj<0 or newj>=3:\n",
    "                            continue\n",
    "                        if newi==3 and newj==0:\n",
    "                            continue\n",
    "                        if newi==3 and newj==2:\n",
    "                            continue\n",
    "                        if i==3 and j==0:\n",
    "                            continue\n",
    "                        if i==3 and j==2:\n",
    "                            continue\n",
    "                        else:                          \n",
    "                            dp[time][i][j] += dp[time-1][newi][newj]\n",
    "                            dp[time][i][j] % (10**9+7)\n",
    "        res = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if (i==3 and j==0) or (i==3 and j==2):\n",
    "                    continue\n",
    "                res = (res+int(dp[n-1][i][j]))%(10**9+7)\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        grid=[[1,2,3],[4,5,6],[7,8,9],[-1,0,-1]]\n",
    "        m,h=4,3\n",
    "        res=0\n",
    "        d={}\n",
    "        def dfs(i,j,n):\n",
    "            if i>=m or i<0 or j>=h or j<0 or grid[i][j]==-1:\n",
    "                return 0\n",
    "            if tuple([i,j,n]) in d.keys():\n",
    "                return d[tuple([i,j,n])]\n",
    "            if n==0: \n",
    "                return 1\n",
    "            ans=0\n",
    "            for x,y in ((i+2,j+1),(i+2,j-1),(i-2,j+1),(i-2,j-1),(i+1,j-2),(i+1,j+2),(i-1,j-2),(i-1,j+2)):\n",
    "                ans=ans+dfs(x,y,n-1)\n",
    "            d[tuple([i,j,n])]=ans%1000000007\n",
    "            return ans%1000000007\n",
    "        for i in range(4):\n",
    "            for j in range(3):\n",
    "                if grid[i][j]!=-1:\n",
    "                    res+=dfs(i,j,n-1)\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N: int) -> int:\n",
    "\n",
    "        def n_num(x: int, n: int) -> int:\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            elif (x, n) in memo:\n",
    "                return memo[(x, n)]\n",
    "            else:\n",
    "                memo[(x, n)] = 0\n",
    "                for y in next_n[x]:\n",
    "                    memo[x,n] += n_num(y, n - 1)\n",
    "                memo[x, n] %= (10 ** 9 + 7)\n",
    "                if x % 3 == 1:\n",
    "                    memo[(x + 2, n)] = memo[x, n]\n",
    "                elif x % 3 == 0 and x > 0:\n",
    "                    memo[(x - 2, n)] = memo[x, n]\n",
    "                return memo[(x, n)]\n",
    "        \n",
    "        next_n = [[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3], [2, 4]]\n",
    "        res = 0\n",
    "        memo = {}\n",
    "        for x in range(10):\n",
    "            res += n_num(x, N - 1)\n",
    "        # print(memo)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N: int) -> int:\n",
    "        memo = dict()\n",
    "        for i in range(10):\n",
    "            memo[(1, i)] = 1\n",
    "        pre = {1: [6, 8], 2: [7, 9], 3:[4, 8], 4: [3, 9, 0], 5:[], 6:[1, 7, 0], 7:[2, 6], 8: [1, 3], 9:[2, 4], 0:[4, 6]}\n",
    "        for i in range(2, N + 1):\n",
    "            for num in range(10):\n",
    "                if num != 5:\n",
    "                    memo[(i, num)] = sum([memo[(i-1, n)] for n in pre[num]])\n",
    "                else:\n",
    "                    memo[(i, num)] = 0\n",
    "        res = 0\n",
    "        for num in range(10):\n",
    "            res += memo[(N, num)]\n",
    "        return res % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "         #if n == 1: return 10\n",
    "        # 类似于棋盘问题\n",
    "        # direction = [[-2,-1],[-2,1],[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2]]\n",
    "        # dp[i][j][k] = dp[i+p][j+q][k-1]\n",
    "        # 注意到由于 * 和 # 不是数字，所以 5 是不可到达的\n",
    "        # 且 dp[4][0][k] = dp[4][2][k] = 0\n",
    "        # 基于对称性，1和3，4和6，7和9作为初始位置得到的结果是一样的\n",
    "        # 注意到:\n",
    "        # dp[7][k] = dp[2][k-1] + dp[6][k-1]\n",
    "        # dp[1][k] = dp[6][k-1] + dp[8][k-1]\n",
    "        # dp[4][k] = dp[3][k-1] + dp[9][k-1] = dp[1][k-1] + dp[7][k-1] = dp[6][k-1]\n",
    "        # dp[2][k] = dp[7][k-1] + dp[9][k-1] = 2 * dp[7][k-1]\n",
    "        # dp[5][k] = 0\n",
    "        # dp[8][k] = dp[1][k-1] + dp[3][k-1] = 2 * dp[1][k-1]\n",
    "        # dp[0][k] = dp[4][k-1] + dp[6][k-1] = 2 * dp[4][k-1] = 2(dp[1][k-2] + dp[7][k-2])\n",
    "        # dp[a][b]表示以a为起点，移动b次得到的组合个数\n",
    "        # 即需要计算的到达所有位置的组合都可以通过dp[1]和dp[7]获得\n",
    "        # 所以仅需要计算dp[1][k] and dp[7][k]\n",
    "        # dp[1][k] = dp[4][k-1] + 2 * dp[1][k-1] = 3*dp[1][k-1] + dp[7][k-1]\n",
    "        # dp[7][k] = 3*dp[7][k-1] + dp[1][k-1]\n",
    "        direction = [[-2, -1], [-2, 1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2]]\n",
    "\n",
    "        def get(dp, i, j, a):\n",
    "            if i < 0 or i > 4 or j < 0 or j > 3 or i == 4 and j == 1 or i == 4 and j == 3:\n",
    "                return 0\n",
    "            return dp[i][j][a]\n",
    "\n",
    "        dp = [[[0] * n for i in range(4)] for j in range(5)]\n",
    "        for k in range(n):\n",
    "            for i in range(1, 5):\n",
    "                for j in range(1, 4):\n",
    "                    if k == 0:\n",
    "                        dp[i][j][k] = 1\n",
    "                    else:\n",
    "                        for p, q in direction:\n",
    "                            dp[i][j][k] += get(dp, i + p, j + q, k - 1)\n",
    "        return (4*dp[1][1][-1] + 2*dp[2][1][-1] + 2*dp[1][2][-1] + dp[4][2][-1] + dp[2][2][-1])%(10**9+7)\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        move = [\n",
    "            [6, 8],\n",
    "            [7, 9],\n",
    "            [4, 8],\n",
    "            [3, 9, 11],\n",
    "            [10, 12],\n",
    "            [1, 7, 11],\n",
    "            [2, 6, 12],\n",
    "            [1, 3],\n",
    "            [2, 4, 10],\n",
    "            [5, 9],\n",
    "            [4, 6],\n",
    "            [5, 7]\n",
    "        ]\n",
    "        dp = [[0 for i in range(12)] for j in range(n)]\n",
    "        dp[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(12):\n",
    "                for k in move[j]:\n",
    "                    if k != 10 and k != 12:\n",
    "                        dp[i][j] += dp[i - 1][k - 1]\n",
    "        return (sum(dp[-1]) - dp[-1][9] - dp[-1][11]) % 1000000007 \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = {}\n",
    "        for i in range(10):\n",
    "            dp[(i, 0)] = 1\n",
    "        for i in range(1,n+1):\n",
    "            dp[(0,i)] = dp[(4,i-1)] + dp[(6,i-1)]\n",
    "            dp[(1,i)] = dp[(6,i-1)] + dp[(8,i-1)]\n",
    "            dp[(2,i)] = dp[(7,i-1)] + dp[(9,i-1)]\n",
    "            dp[(3, i)] = dp[(4, i - 1)] + dp[(8, i - 1)]\n",
    "            dp[(4, i)] = dp[(0, i - 1)] + dp[(3, i - 1)]+ dp[(9, i - 1)]\n",
    "            dp[(5, i)] = 0\n",
    "            dp[(6, i)] = dp[(0, i - 1)] + dp[(1, i - 1)] + dp[(7, i - 1)]\n",
    "            dp[(7, i)] = dp[(2, i - 1)] + dp[(6, i - 1)]\n",
    "            dp[(8, i)] = dp[(1, i - 1)] + dp[(3, i - 1)]\n",
    "            dp[(9, i)] = dp[(2, i - 1)] + dp[(4, i - 1)]\n",
    "            dp[(0, i)] = dp[(4, i - 1)] + dp[(6, i - 1)]\n",
    "        return sum([dp[(i, n-1)] % (10**9+7) for i in range(10)])  % (10**9+7) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = {}\n",
    "        dp[(0, 0)] = 1\n",
    "        dp[(1, 0)] = 1\n",
    "        dp[(2, 0)] = 1\n",
    "        dp[(3, 0)] = 1\n",
    "        dp[(4, 0)] = 1\n",
    "        dp[(5, 0)] = 1\n",
    "        dp[(6, 0)] = 1\n",
    "        dp[(7, 0)] = 1\n",
    "        dp[(8, 0)] = 1\n",
    "        dp[(9, 0)] = 1\n",
    "        for i in range(1,n+1):\n",
    "            dp[(0,i)] = dp[(4,i-1)] + dp[(6,i-1)]\n",
    "            dp[(1,i)] = dp[(6,i-1)] + dp[(8,i-1)]\n",
    "            dp[(2,i)] = dp[(7,i-1)] + dp[(9,i-1)]\n",
    "            dp[(3, i)] = dp[(4, i - 1)] + dp[(8, i - 1)]\n",
    "            dp[(4, i)] = dp[(0, i - 1)] + dp[(3, i - 1)]+ dp[(9, i - 1)]\n",
    "            dp[(5, i)] = 0\n",
    "            dp[(6, i)] = dp[(0, i - 1)] + dp[(1, i - 1)] + dp[(7, i - 1)]\n",
    "            dp[(7, i)] = dp[(2, i - 1)] + dp[(6, i - 1)]\n",
    "            dp[(8, i)] = dp[(1, i - 1)] + dp[(3, i - 1)]\n",
    "            dp[(9, i)] = dp[(2, i - 1)] + dp[(4, i - 1)]\n",
    "            dp[(0, i)] = dp[(4, i - 1)] + dp[(6, i - 1)]\n",
    "        ret = 0\n",
    "        for i in range(10):\n",
    "            ret += dp[(i, n-1)]\n",
    "        return ret % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        mod = pow(10, 9) + 7\n",
    "\n",
    "        def noverflow(i: int, j: int) -> bool:\n",
    "            ret = 0 <= i < 3 and 0 <= j < 3\n",
    "            return ret or (i == 3 and j == 1)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dpf(i: int, j: int, n: int) -> int:\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            else:\n",
    "                offs = [(i + 1, j + 2),\n",
    "                        (i + 1, j - 2),\n",
    "                        (i - 1, j + 2),\n",
    "                        (i - 1, j - 2),\n",
    "                        (i + 2, j + 1),\n",
    "                        (i + 2, j - 1),\n",
    "                        (i - 2, j + 1),\n",
    "                        (i - 2, j - 1)]\n",
    "                return sum([dpf(off[0], off[1], n - 1) % mod for off in offs if noverflow(off[0], off[1])]) % mod\n",
    "\n",
    "        ret = 0\n",
    "        ret += sum([dpf(i, j, n) % mod for i in range(3) for j in range(3)]) % mod\n",
    "        ret += dpf(3, 1, n) % mod\n",
    "        return ret % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        dic={0:[4,6],1:[6,8],2:[7,9],3:[4,8],4:[0,3,9],5:[],6:[0,1,7],7:[2,6],8:[1,3],9:[2,4]}\n",
    "        def helper(cur,k):\n",
    "            if k==1:\n",
    "                return sum(cur.values())\n",
    "            new={key:0 for key in cur.keys()}\n",
    "            for key in cur.keys():\n",
    "                next=dic[key]\n",
    "                for val in next:\n",
    "                    new[val]+=cur[key]\n",
    "            return helper(new,k-1)\n",
    "        return helper({key:1 for key in dic.keys()},n) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        numMap = [[4,6],[6,8],[7,9],[4,8],[0,3,9],[],[0,1,7],[2,6],[1,3],[2,4]]\n",
    "        memo = {}\n",
    "        def dp(num, n):\n",
    "            if(n == 1):\n",
    "                return 1\n",
    "            if((num,n) in memo):\n",
    "                return memo[(num,n)] % M\n",
    "            res = 0\n",
    "            for d in numMap[num]:\n",
    "                res += dp(d,n-1) % M\n",
    "            memo[(num,n)] = res % M\n",
    "            return memo[(num,n)]\n",
    "        result = 0\n",
    "        for i in range(10):\n",
    "            result += dp(i,n) % M\n",
    "        return result % M\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 10\n",
    "\n",
    "        digit_mp = {1: [6, 8],\n",
    "                    2: [7, 9],\n",
    "                    3: [4, 8],\n",
    "                    4: [3, 9, 0],\n",
    "                    6: [1, 7, 0],\n",
    "                    7: [2, 6],\n",
    "                    8: [1, 3],\n",
    "                    9: [2, 4],\n",
    "                    0: [4, 6]}\n",
    "\n",
    "        #  以num开头的 长度为n的号码数\n",
    "        @cache\n",
    "        def dfs(num: int, n: int) -> int:\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            elif n == 2:\n",
    "                return len(digit_mp[num])\n",
    "\n",
    "            res = 0\n",
    "            for x in digit_mp[num]:\n",
    "                res += dfs(x, n - 1)\n",
    "\n",
    "            return res % (10 ** 9 + 7)\n",
    "\n",
    "        return sum(dfs(x, n) for x in digit_mp.keys()) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAPPING = {1:[6, 8], 2:[7, 9], 3:[4, 8], 4:[3, 9, 0], 5:[], 6:[1, 7, 0], 7:[2, 6], 8:[1, 3], 9:[2, 4], 0:[4, 6]}\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, cur) -> int: #第 i 次跳跃是从数字 cur 开始的方案个数\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if MAPPING[cur] is None:\n",
    "                return 0\n",
    "            for nxt in MAPPING[cur]:\n",
    "                res += dfs(i + 1, nxt)\n",
    "            return res % MOD\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return sum(dfs(1, fir) for fir in range(10)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        nextnum = {1:[6,8],2:[7,9],3:[4,8],4:[0,3,9],6:[0,1,7],7:[2,6],8:[1,3],9:[2,4],0:[4,6]}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(num,step):\n",
    "            if step==1: return 1\n",
    "            res = 0\n",
    "            for nnum in nextnum[num]:\n",
    "                res+=dp(nnum,step-1)\n",
    "            return res%mod\n",
    "        \n",
    "        ans = 0\n",
    "        if n==1: return 10\n",
    "        for i in range(10):\n",
    "            if i!=5:\n",
    "                ans+=dp(i,n)%mod\n",
    "        \n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        # loop each number -> dfs\n",
    "        # Memoization\n",
    "        neighbors = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8], \n",
    "                    4: [0, 3, 9], 5: [], 6: [0, 1, 7], \n",
    "                    7: [2, 6], 8: [1, 3], 9: [2, 4]}\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(i,n): \n",
    "            if (i,n) in cache: \n",
    "                return cache[(i,n)]\n",
    "            if n == 1: \n",
    "                return 1\n",
    "            ans = 0\n",
    "            for nei in neighbors[i]: \n",
    "                ans += dfs(nei,n-1)\n",
    "            cache[(i,n)] = ans % (10**9 + 7)\n",
    "            return cache[(i,n)]\n",
    "        \n",
    "        res = [dfs(i,n) for i in range(10)]\n",
    "        return sum(res) % (10**9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # DP \n",
    "        # dp = [1] * 10 #dp[i]: number of ways to go i \n",
    "        # for _ in range(n-1): # iterate n-1 times so that total n-1 steps\n",
    "        #     cur_dp = [0] * 10\n",
    "        #     for src in range(10): \n",
    "        #         for dst in neighbors[src]:\n",
    "        #             cur_dp[dst] += dp[src] \n",
    "        #             #num of ways to go to dst using n steps = num of ways to go to src using n-1 steps \n",
    "        #             #and there could be several sources, so += \n",
    "        #             cur_dp[dst] %= (10**9 + 7)\n",
    "        #     print(cur_dp)\n",
    "        #     # 每走一次，更新dp\n",
    "        #     dp = cur_dp\n",
    "        # return sum(dp) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        jump_grids = {\n",
    "            0: [4, 6],\n",
    "            1: [6, 8],\n",
    "            2: [7, 9],\n",
    "            3: [4, 8],\n",
    "            4: [0, 3, 9],\n",
    "            5: [],\n",
    "            6: [0, 1, 7],\n",
    "            7: [2, 6],\n",
    "            8: [1, 3],\n",
    "            9: [2, 4],\n",
    "        }\n",
    "\n",
    "        @cache\n",
    "        def helper(start: int, number_cnt: int) -> int:\n",
    "            if number_cnt == 1:\n",
    "                return 1\n",
    "            \n",
    "            return sum([helper(next_num, number_cnt - 1) for next_num in jump_grids[start]]) % MOD\n",
    "            \n",
    "        return sum([helper(start, n) for start in range(10)]) % MOD\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# ! 想知道记忆化搜索能否做出来\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        self.DICT = {1:[6,8], 2:[7,9], 3:[4,8], 4:[3,9,0], 5:[], 6:[1,7,0], 7:[2,6], 8:[1,3], 9:[2,4], 0:[4,6]}\n",
    "        @functools.lru_cache(None)\n",
    "        def memorydfs(n, num):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for item in self.DICT[num]:\n",
    "                cnt += memorydfs(n-1, item)\n",
    "            return cnt % (10**9 + 7)\n",
    "        cnt = 0\n",
    "        for i in range(10):\n",
    "            cnt += memorydfs(n-1, i)\n",
    "        return cnt % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return [1] * 10\n",
    "\n",
    "            last = dfs(i-1)\n",
    "            cur = [0] * 10\n",
    "            cur[0] = last[4] + last[6]\n",
    "            cur[1] = last[8] + last[6]\n",
    "            cur[2] = last[7] + last[9]\n",
    "            cur[3] = last[8] + last[4]\n",
    "            cur[4] = last[3] + last[9] + last[0]\n",
    "            cur[5] = 0\n",
    "            cur[6] = last[1] + last[7] + last[0]\n",
    "            cur[7] = last[6] + last[2]\n",
    "            cur[8] = last[1] + last[3]\n",
    "            cur[9] = last[2] + last[4]\n",
    "            for i in range(10):\n",
    "                cur[i] = cur[i] % MOD\n",
    "            return cur\n",
    "\n",
    "        v = dfs(n-1)\n",
    "        return sum(v) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, move):\n",
    "            if move == 0:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for di, dj in [(2,1), (1,2), (2,-1), (-2,1), (1,-2),(-1,2),(-2,-1),(-1,-2)]:\n",
    "                newi, newj = i + di, j + dj\n",
    "\n",
    "                if 0 <= newi < 4 and 0 <= newj < 3 and (newi, newj) not in [(3,0), (3,2)]:\n",
    "                    ans += dp(newi, newj, move - 1)\n",
    "                    ans %= mod\n",
    "\n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                ans += dp(i, j, n - 1)\n",
    "                ans %= mod\n",
    "        \n",
    "\n",
    "        ans += dp(3, 1, n - 1)\n",
    "        ans %= mod\n",
    "\n",
    "        return ans\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        r = 4\n",
    "        c = 3\n",
    "        notIn = [(3, 0), (3, 2)]\n",
    "        step1 = [(2, 0), (-2, 0), (0, 2), (0, -2)]\n",
    "        step2 = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y, num):\n",
    "            if num == 0:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(4):\n",
    "                newX = step1[i][0] + x     \n",
    "                newY = step1[i][1] + y\n",
    "                if newX < 0 or newX >= r or newY < 0 or newY >= c:\n",
    "                    continue\n",
    "\n",
    "                if i % 2 == 1:\n",
    "                    js = [i - 1, i]\n",
    "                else:\n",
    "                    js = [i, i + 1] \n",
    "\n",
    "                for j in js: \n",
    "                    newXX = newX + step2[j][0]\n",
    "                    newYY = newY + step2[j][1]\n",
    "                    if newXX < 0 or newXX >= r or newYY < 0 or newYY >= c or (newXX, newYY) in notIn:\n",
    "                        continue\n",
    "                    ans += dfs(newXX, newYY, num - 1) \n",
    "                    ans %= MOD  \n",
    "\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(4):\n",
    "            for j in range(3):\n",
    "                if (i, j) not in notIn:\n",
    "                    ans += dfs(i, j, n - 1)\n",
    "                    ans %= MOD\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        g = [[4,6],[8,6],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]\n",
    "        @cache\n",
    "        def dfs(i,n):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            return sum(dfs(j,n - 1) for j in g[i]) % MOD\n",
    "        \n",
    "        return sum(dfs(i,n - 1) for i in range(10)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j,cnt):\n",
    "            if cnt==n:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for di,dj in (-2,-1),(-2,1),(-1,2),(-1,-2),(2,-1),(2,1),(1,2),(1,-2):\n",
    "                ni,nj=i+di,j+dj\n",
    "                if 0<=ni<4 and 0<=nj<3 and grid[ni][nj].isdigit():\n",
    "                    ans=(ans+dfs(ni,nj,cnt+1))%Mod\n",
    "            return ans\n",
    "        res=0\n",
    "        Mod=10**9+7\n",
    "        grid=[['1','2','3'],['4','5','6'],['7','8','9'],['*','0','#']]\n",
    "        for i in range(4):\n",
    "            for j in range(3):\n",
    "                if grid[i][j].isdigit():\n",
    "                    res+=dfs(i,j,1)\n",
    "        return res%Mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        # 状态和选择\n",
    "        # 状态：n和当前的数字\n",
    "        # dp[i][j] 表示 第 i 步，所在位置数字为 j 的不同号码数\n",
    "        dp = [[0] * 10 for _ in range(n)]\n",
    "        # 初始化\n",
    "        for j in range(10):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][4] + dp[i-1][6]\n",
    "            dp[i][1] = dp[i-1][6] + dp[i-1][8]\n",
    "            dp[i][2] = dp[i-1][7] + dp[i-1][9]\n",
    "            dp[i][3] = dp[i-1][4] + dp[i-1][8]\n",
    "            dp[i][4] = dp[i-1][3] + dp[i-1][9] + dp[i-1][0]\n",
    "            dp[i][6] = dp[i-1][1] + dp[i-1][7] + dp[i-1][0]\n",
    "            dp[i][7] = dp[i-1][2] + dp[i-1][6]\n",
    "            dp[i][8] = dp[i-1][1] + dp[i-1][3]\n",
    "            dp[i][9] = dp[i-1][2] + dp[i-1][4]\n",
    "        # print(dp)\n",
    "        return sum(dp[-1]) % (10**9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        graph = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]\n",
    "        m = [[None for __ in range(N-1)] for _ in range(10)]\n",
    "        \n",
    "        def dfs(cur, N):\n",
    "            if N == 0:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nei in graph[cur]:\n",
    "                if m[nei][N-1] is not None:\n",
    "                    cnt += m[nei][N-1]\n",
    "                else:\n",
    "                    m[nei][N-1] = dfs(nei, N-1)\n",
    "                    cnt += m[nei][N-1]\n",
    "            return cnt % (1e9+7)\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(10):\n",
    "            cnt += dfs(i, N-1)\n",
    "            cnt %= (1e9+7)\n",
    "        return int(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        graph = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]\n",
    "        m = [[None for __ in range(N-1)] for _ in range(10)]\n",
    "        \n",
    "        def dfs(cur, N):\n",
    "            if N == 0:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nei in graph[cur]:\n",
    "                if m[nei][N-1] is not None:\n",
    "                    cnt += m[nei][N-1]\n",
    "                else:\n",
    "                    m[nei][N-1] = dfs(nei, N-1)\n",
    "                    cnt += m[nei][N-1]\n",
    "            return cnt % 1000000007\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(10):\n",
    "            cnt += dfs(i, N-1)\n",
    "            cnt %= 1000000007\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, n: int) -> int:\n",
    "        directions = [[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-2, 1], [-2, -1], [-1, -2]]\n",
    "        panel = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [\"#\", 0, \"#\"]]\n",
    "        self.memo = dict()\n",
    "        \n",
    "        def is_valid(i, j):\n",
    "            return 0 <= i < 4 and 0 <= j < 3 and panel[i][j] != \"#\"\n",
    "        \n",
    "        def dfs(n, i, j):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if str(n)+str(i)+str(j) in self.memo:\n",
    "                return self.memo[str(n)+str(i)+str(j)]\n",
    "\n",
    "            res = 0\n",
    "            for di, dj in directions:\n",
    "                newi, newj = i+di, j+dj\n",
    "                if is_valid(newi, newj):\n",
    "                    res += dfs(n-1, newi, newj)\n",
    "            self.memo[str(n)+str(i)+str(j)] = res\n",
    "            return self.memo[str(n)+str(i)+str(j)] % (10**9+7)\n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(len(panel)):\n",
    "            for j in range(len(panel[0])):\n",
    "                if is_valid(i, j):\n",
    "                    ans += dfs(n-1, i, j)\n",
    "        \n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightDialer(self, k: int) -> int:\n",
    "        @cache\n",
    "        def g(i,j,t):\n",
    "           if t==0:\n",
    "               return 1\n",
    "           res=0     \n",
    "           for a,b in  [[2,1],[2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[-2,-1],[-2,1]]:\n",
    "               x=i+a\n",
    "               y=j+b\n",
    "               if 0<=x<n and 0<=y<m and (x,y)!=(3,0) and (x,y)!=(3,2):\n",
    "                   res+=g(x,y,t-1)\n",
    "           return res\n",
    "        n=4\n",
    "        m=3\n",
    "        ans =0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "              if (i,j)!=(3,0) and (i,j)!=(3,2):\n",
    "                ans+=g(i,j,k-1)           \n",
    "        return ans%(10**9+7)    \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
